﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

class Sol113
{



    public IList<IList<int>> PathSum2(TreeNode root, int targetSum)//BFS
    {

        IList<TreeNode> queueNode = new List<TreeNode>();
        IList<int> queueSum = new List<int>();//记录各个叶子节点的sum,不仅要记录sum，还有记录路径
        IList<IList<int>> queueList = new List<IList<int>>();//记录各个叶子节点的sum,不仅要记录sum，还有记录路径
        IList<IList<int>> res = new List<IList<int>>();

        if (root == null)
        {
            return res;
        }


        queueNode.Add(root);
        queueSum.Add(root.val);

        queueList.Add(queueSum);

        while (queueNode.Count > 0)
        {
            //出队
            root = queueNode[0];
            int curSum = queueSum[0];
            IList<int> queueLeft = new List<int>(queueList[0]);
            IList<int> queueRight = new List<int>(queueList[0]);
            IList<int> queue = new List<int>(queueList[0]);

            if (root.left == null && root.right == null)
            { //叶子节点，判断一下

                if (curSum == targetSum)//符合条件的留在队里
                {
                    res.Add(queue);
                    //Console.WriteLine(curSum );
                }


            }

            //sum=sum + root.val;//不可以加入到一个总共里面，只能加入对应路径的
            Console.WriteLine("val:   " + root.val + "    sum: " + curSum);
            queueNode.RemoveAt(0);
            queueSum.RemoveAt(0);
            queueList.RemoveAt(0);
            if (root.left != null)
            {
                queueNode.Add(root.left);//叶子节点入队的同时 ，对应的sum也入队
                queueSum.Add(root.left.val + curSum);
                queueLeft.Add(root.left.val);
                queueList.Add(queueLeft);
            }
            if (root.right != null)
            {
                queueNode.Add(root.right);
                queueSum.Add(root.right.val + curSum);

                queueRight.Add(root.right.val);

                queueList.Add(queueRight);
            }

            //for (int i = 0; i < queueList.Count; i++)
            //{

            //    for (int j = 0; j < queueList[i].Count; j++)
            //    {
            //        Console.Write(queueList[i][j]+ "  ");
            //    }
            //    Console.WriteLine( );

            //}

        }


        return res;

    }
    public IList<IList<int>> PathSum3(TreeNode root, int targetSum)//BFS,使用哈希表记录父亲（每个子树节点只有一个父亲）
    {
        IList<TreeNode> queueNode = new List<TreeNode>();
        IList<int> queueSum = new List<int>();//记录各个叶子节点的sum
        Dictionary<TreeNode,TreeNode> parent = new Dictionary<TreeNode,TreeNode>();//key是child，value是父亲
        IList<IList<int>> res = new List<IList<int>>();
        if (root == null)
        {
            return res;
        }


        queueNode.Add(root);
        queueSum.Add(root.val);
        while (queueNode.Count > 0)
        {
            //出队
            root = queueNode[0];
            int curSum = queueSum[0];
            if (curSum == targetSum)
            {
                if (root.left == null && root.right == null)
                { //叶子节点，判断一下


                    //有路径满足条件
                    getPath(parent,root, res);

                }
            }
            //sum=sum + root.val;//不可以加入到一个总共里面，只能加入对应路径的
            //Console.WriteLine("val:   " + root.val + "    sum: " + curSum);
            queueNode.RemoveAt(0);
            queueSum.RemoveAt(0);
            if (root.left != null)
            {
                parent[root.left] = root;
                queueNode.Add(root.left);//叶子节点入队的同时 ，对应的sum也入队
                queueSum.Add(root.left.val + curSum);
            }
            if (root.right != null)
            {
                parent[root.right] = root;
                queueNode.Add(root.right);
                queueSum.Add(root.right.val + curSum);
            }



        }


        return res;
    }

    private void getPath(Dictionary<TreeNode, TreeNode> parent, TreeNode root, IList<IList<int>> res)
    {
        IList<int> path = new List<int>();


        while (parent.ContainsKey(root))

        {
            path.Add(root.val);
            root = parent[root];//向上找父亲
        }
        path.Add(root.val);//单独处理一下root
        path.Reverse();


        res.Add(path);
    }

    IList<int> path = new List<int>();
    IList<IList<int>> res = new List<IList<int>>();
    public IList<IList<int>> PathSum(TreeNode root, int targetSum)//DFS,递归
    {
      
        dfs(root, targetSum);
        return res;
    }

    private void dfs(TreeNode root, int targetSum)
    {
        if (root == null)
        {
            return;
        }


        path.Add(root.val);
        if (root.left == null&&root.right==null) { 
        
        if(root.val==targetSum)
            {
                //res.Add(path);//这里添加的是引用，所以后面path被改变的时候，res里面的也会被修改
                res.Add(new List<int>(path));
            }
        
        }
       

        dfs(root.left, targetSum- root.val);
        dfs(root.right, targetSum- root.val);
        path.Remove(root.val);

    }
}
class Program113
{

    static void Main113(string[] args)
    {
        string preOrder = "5 4 11 7 2 8 13 4 5 1";
        string[] chars = preOrder.Split(" ");
        int[] nums = new int[chars.Length];
        for (int i = 0; i < chars.Length; i++)
        {
            nums[i] = int.Parse(chars[i]);
        }

        int[] inOrder = { 7, 11, 2, 4, 5, 13, 8,5, 4, 1 };

        Solution105 solution105 = new Solution105();



        TreeNode root = solution105.BuildTree(nums, inOrder);

        //solution105.levelOrder(root);
        Sol113 solution = new Sol113();
        IList<IList<int>> res = solution.PathSum(root, 22);
       for (int i = 0;i < res.Count;i++) {
        
        for (int j = 0;j < res[i].Count; j++)
            {
                Console.Write(res[i][j] + "  ");
            }
            Console.WriteLine();

        }

    }
}